#include"Sort.h"

void Print(int* arr, int len)
{
	for (int i = 0; i < len; i++)
	{
		printf("%d ", arr[i]);
	}
}

void verify(int* arr, int n)
{
	for (int i = 1; i < n; i++)
	{
		assert(arr[i] >= arr[i - 1]);
	}
}

int* numcreate(int n)
{
	int* arr = (int*)malloc(sizeof(int) * n);
	assert(arr);
	return arr;
}

int cmp(const void* a, const void* b)
{
	return *(int*)a - *(int*)b;
}

void test_Sort()
{
	int n = 10000000;
	int* arr = (int*)malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++)
	{
		arr[i] = rand();
	}

	//int arr[] = { 9,5,1,3,1,1,1,1,2,1,8,8,90,0};
	//int n = sizeof(arr) / sizeof(arr[0]);

	MergeSort(arr,n);


	verify(arr, n);
}

test()
{
	int n = 10000000;
	int* arr1 = numcreate(n);
	int* arr2 = numcreate(n);
	int* arr3 = numcreate(n);
	int* arr4 = numcreate(n);
	int* arr5 = numcreate(n);
	int* arr6 = numcreate(n);
	int* arr7 = numcreate(n);
	int* arr8 = numcreate(n);
	int* arr9 = numcreate(n);
	int* arr10 = numcreate(n);

	for (int i = 0; i < n; i++)
	{
		arr8[i]=arr7[i]=arr6[i]=arr5[i] = arr4[i] = arr3[i]
		=arr9[i]=arr10[i] = arr2[i] = arr1[i] = rand();
	}

	int begin1 = clock();
	//InsertSort(arr1, n);
	int end1 = clock();

	int begin2 = clock();
	ShellSort(arr2, n);
	int end2 = clock();

	int begin3 = clock();
	//qsort(arr3, n, sizeof(int), cmp);
	int end3 = clock();

	int begin4 = clock();
	HeapSort(arr4, n);
	int end4 = clock();

	int begin5 = clock();
	//bubbleSort(arr5, n);
	int end5 = clock();

	int begin6 = clock();
	QuickSort1(arr6, 0, n - 1);
	int end6 = clock();
	

	int begin7 = clock();
	MergeSort(arr7, n);
	int end7 = clock();

	int begin8 = clock();
	QuickSortNonR(arr8,0, n-1);
	int end8 = clock();

	int begin9 = clock();
	QuickSort2(arr9,0, n-1);
	int end9 = clock();

	int begin10 = clock();
	QuickSort2(arr10,0, n-1);
	int end10 = clock();


	printf("Insertsort : %d\n", end1 - begin1);
	printf("ShellSort  : %d\n", end2 - begin2);
	printf("qsort      : %d\n", end3 - begin3);
	printf("HeapSort   : %d\n", end4 - begin4);
	printf("bubbleSort : %d\n", end5 - begin5);
	printf("QuickSort1: %d\n", end6 - begin6);
	printf("QuickSort2: %d\n", end9 - begin9);
	printf("QuickSort3: %d\n", end10 - begin10);
	printf("MergeSort  : %d\n", end7 - begin7);
	printf("QuickSortNonR: %d\n", end8 - begin8);


	free(arr1);
	free(arr2);
	free(arr3);
	free(arr4);
	free(arr5);
	free(arr6);
	free(arr7);
	free(arr8);
	free(arr9);
	free(arr10);
}

tesft()
{
	int n = 1000000;
	int* arr1 = numcreate(n);
	int* arr2 = numcreate(n);


	for (int i = 0; i < n; i++)
	{
		arr2[i] = arr1[i] = rand();
	}

	int begin1 = clock();
	HeapSort(arr1, n);
	int end1 = clock();

	int begin2 = clock();
	ShellSort(arr2, n);
	int end2 = clock();

	printf("HeapSort : %d\n", end1 - begin1);
	printf("ShellSort  : %d\n", end2 - begin2);

	free(arr1);
	free(arr2);
}

void Ultimate_Test()
{
	int n = 10000000, count = 100;
	int timeShell = 0, timeHeap = 0;
	for (int a = 0; a < count; a++)
	{
		int* arr1 = numcreate(n);
		int* arr2 = numcreate(n);
		for (int i = 0; i < n; i++) 
			arr1[i] = arr2[i] = rand() + i;

		int begin1 = clock();
		ShellSort(arr1, n);
		int end1 = clock();

		int begin2 = clock();
		HeapSort(arr2, n);
		int end2 = clock();

		timeShell += end1 - begin1;
		timeHeap += end2 - begin2;

		free(arr1);
		free(arr2);
	}

	printf("ShellSort : %.2f\n", 1.0 * timeShell / count);
	printf("HeapSort  : %.2f\n", 1.0 * timeHeap / count);

}

void _test()
{
	int n = 100000000;
	int* arr = (int*)malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++)
	{
		arr[i] = rand();
	}
	CountSort(arr, n);
	verify(arr, n);
	free(arr);
}

void Test_QuickSort()
{
	int n = 5000000;
	int* arr1 = numcreate(n);
	int* arr2 = numcreate(n);
	int* arr3 = numcreate(n);

	for (int i = 0; i < n; i++)
	{
		arr3[i] = arr2[i] = arr1[i] = rand();
	}

	int begin1 = clock();
	QuickSort1(arr1, 0, n - 1);
	int end1 = clock();

	int begin2 = clock();
	QuickSort2(arr2, 0, n - 1);
	int end2 = clock();

	int begin3 = clock();
	QuickSort3(arr3, 0, n - 1);
	int end3 = clock();

	verify(arr1, n);
	verify(arr2, n);
	verify(arr3, n);

	printf("QuickSort1: %d\n", end1 - begin1);
	printf("QuickSort2: %d\n", end2 - begin2);
	printf("QuickSort3: %d\n", end3 - begin3);

	free(arr1);
	free(arr2);
	free(arr3);
}

void Test_MergeSort_CountSort()
{
	int n = 10000000;
	int count = 100;
	int* arr1 = numcreate(n);
	int* arr2 = numcreate(n);
	int* arr3 = numcreate(n);
	int time1 = 0, time2 = 0, time3 = 0;
	int tmp = count;
	while (tmp--)
	{

		int i = 0;
		for (i = 0; i < n; i++)
		{
			if (rand() % 2)
			{
				arr3[i] = arr2[i] = arr1[i] = -rand() + i;
			}
			else
			{
				arr3[i] = arr2[i] = arr1[i] = rand() - i;
			}
		}

		int begin1 = clock();
		MergeSort(arr1, n);
		int end1 = clock();

		int begin2 = clock();
		MergeSortNonR(arr2, n);
		int end2 = clock();

		int begin3 = clock();
		CountSort(arr3, n);
		int end3 = clock();

		time1 += end1 - begin1;
		time2 += end2 - begin2;
		time3 += end3 - begin3;

	}
	printf("MergeSort: %.2f\n", (float)time1/count);
	printf("MergeSortNonR: %.2f\n", (float)time2 / count);
	printf("CountSort: %.2f\n", (float)time3 / count);
	free(arr1);
	free(arr2);
	free(arr3);
}

int main()
{
	srand((unsigned int)time(NULL));
	//Ultimate_Test();
	//test();
	//Test_QuickSort();
	Test_MergeSort_CountSort();
	//_test();

	return 0;
}

